'''
时间复杂度：算法运行所占用的时间
空间复杂度：算法运行所占用的空间
冒泡排序、选择排序、归并排序、快序排序、插入排序
'''

'''
冒泡排序：通过遍历比较相邻的值的大小
具体的实现步骤如下： 
1. 从第一个元素开始依次比较相邻的两个元素的大小。 
2. 如果前一个元素比后一个元素大，则交换这两个元素的位置。 
3. 继续向后比较，直到将整个集合中的所有元素都比较一遍。 
4. 重复1-3步，直到整个集合都被排序。
该算法的时间复杂度为O(n^2)，效率较低。但是它的实现简单易懂，适用于小规模的数据排序。
'''
#代码实现



def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

'''
增加了一个名为`flag`的标志变量，用来指示是否有元素交换。
在内层循环中，如果有元素交换，就将标志变量设为True；
在外层循环中，如果标志变量仍然为False，说明已经排好序，直接退出循环即可。 
这样，就可以对已经排好序的数组不再循环，从而提高排序效率。
'''
def bubble_sort1(arr):
    n = len(arr)
    for i in range(n):
        # 标志变量
        flag = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                # 如果有元素交换，就将标志变量设为True
                flag = True
        # 如果没有元素交换，说明已经排好序，直接退出循环
        if not flag:
            break
    return arr


arr = [2,3,2,24,25,56,3,32,7,8,534,6,4,7]
print("排序后的数组：",bubble_sort1(arr))